package 华为OD机试真题2023.进阶题;

import utils.MyUtil;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class HJ28_硬件产品销售方案 {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new File("src/main/java/华为OD机试真题2023/进阶题/input/28.txt"));
        MyUtil.START();
        Solution(in);
        //        Solution2(in);
        MyUtil.END();
    }

    static LinkedList<Integer> tmp = new LinkedList<>();
    static List<LinkedList<Integer>> result = new ArrayList<>();

    static void Solution(Scanner in) {
        int target = in.nextInt();
        in.nextLine(); // 吸收回车
        String[] sArray = in.nextLine().replaceAll("\\[", "").replaceAll("]", "").split(", ");
        int[] prices = new int[sArray.length];
        for (int i = 0; i < sArray.length; i++) {
            prices[i] = Integer.parseInt(sArray[i]);
        }
        Arrays.sort(prices);
        dfs(prices, 0, target);
//        Collections.reverse(result); //例题的输出是这样的
        System.out.println(result.toString());
    }

    static void dfs(int[] prices, int startIndex, int target) {
        if (target == 0) {
            result.add(new LinkedList<>(tmp));
            return;
        }
        if (startIndex == prices.length) {
            return;
        }
        int now = prices[startIndex];
        for (int i = 0; i * now <= target; i++) {
            for (int j = 0; j < i; j++) {
                tmp.addLast(now);
            }
            dfs(prices, startIndex + 1, target - i * now);
            for (int j = 0; j < i; j++) {
                tmp.removeLast();
            }
        }
    }

    static void Solution2(Scanner in) {
        int amount = Integer.valueOf(in.nextLine());
        String input = in.nextLine().replaceAll("\\s", "");
        input = input.substring(1, input.length() - 1);
        String[] arr = input.split(",");
        int[] prices = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            prices[i] = Integer.valueOf(arr[i]);
        }
        Arrays.sort(prices);
        Stack<Integer> st = new Stack<>();
        List<List<Integer>> ans = new ArrayList<>();
        dfs2(prices, amount, st, ans, 0);
        System.out.println(ans);
    }

    public static void dfs2(
            int[] prices, int amout, Stack<Integer> st, List<List<Integer>> ans, int index) {
        if (amout == 0) {
            ans.add(new ArrayList<Integer>(st));
            return;
        }
        if (amout < prices[0]) return;

        for (int i = index; i < prices.length; i++) {
            int price = prices[i];
            st.push(price);
            dfs2(prices, amout - price, st, ans, i);
            st.pop();
        }
    }
}
